#include <iostream>
#include <functional>
#include <string>
#include <vector>
#include <stack>
#include <list>
#include <map>
using namespace std;

struct Node {
	int t;
	int val;
	Node(int a, int b) :t(a), val(b) {}
};

int main()
{
	string type; cin >> type; //cout << type << endl;
	bool DUN = 0, GN = 0; // 有向无向、带不带权
	if (type == "DG")  DUN = 1, GN = 0;
	if (type == "DN")  DUN = 1, GN = 1;
	if (type == "UDG") DUN = 0, GN = 0;
	if (type == "UDN") DUN = 0, GN = 1;
	int n; cin >> n; vector<string> nodes(n);
	map<string, int> ntoi; // node to index
	for (int i = 0; i < n; i++) {
		cin >> nodes[i]; if (i) cout << ' '; cout << nodes[i];
		ntoi[nodes[i]] = i;
	}	cout << endl;
	string flag("0"); vector<list<Node>> graph(n);
	int k; cin >> k; //cout << k << endl;
	vector<vector<int>> path(k, vector<int>(2 + GN)); // 带权的话 给权值留个位置
	for (int i = 0; i < k; i++) cin >> path[i][0] >> path[i][1];
	if (GN) for (int i = 0; i < k; i++)  cin >> path[i][2];
	for (auto& v : path) {
		graph[v[0]].push_front(Node(v[1], (GN ? v[2] : 0)));
		if (!DUN) graph[v[1]].push_front(Node(v[0], (GN ? v[2] : 0)));
	}
	for (int i = 0; i < n; i++) {
		if (i)cout << endl;
		cout << nodes[i];
		for (auto e : graph[i]) {
			cout << "->" << e.t;
			if (GN) cout << "(" << e.val << ")";
		}
		//cout << "->nullptr";
	}

	cout << "\n\n";

	int start, m; cin >> start >> m; m++;
	vector<int> visited(n);
	vector<vector<int>> paths;
	vector<int> curpath;
	function<void(int)>
		dfs = [&](int cur) {
		if (curpath.size() == m) {
			paths.emplace_back(curpath.begin(), curpath.end());
			return;
		}
		for (auto e : graph[cur]) {
			if (visited[e.t]) continue;
			visited[e.t] = true;
			curpath.push_back(e.t);
			dfs(e.t);
			curpath.pop_back();
			visited[e.t] = false;
		}
		};

	if (start >= 0 && start < n) {
		visited[start] = true;
		curpath.push_back(start);
		dfs(start);
	}

	for (int i = 0; i < paths.size(); i++) {
		for (int j = 0; j < paths[i].size(); j++) {
			if (j) cout << "->";
			cout << nodes[paths[i][j]];
		}
		cout << endl;
	}

	cout << paths.size();

	return 0;
}